package org.raymond.iworks.study.basic.algorithm.sort;

/**
 * @author raymond
 * @version V1.0
 */

import java.util.Arrays;

/**
 * 希尔排序:
 * 也是一种插入排序,改进了简单插入排序的问题,也称缩小增量排序
 * 基本思想:
 * 把记录按下标的一定增量分组,对每组使用直接插入排序算法排序;随着增量逐渐减少,每组包含的关键词越来越多,
 * 当增量减至1时,整个文件恰被分成一组,算法便终止
 *
 * 示例:
 * init: [8, 9, 1, 7, 2, 3, 5, 4, 6, 0]
 * 设初始增量gap=length/2=5,
 * 则整个数组被分为5组: [8, 3] [9, 5], [1, 4], [7, 6], [2, 0]
 * 对这5组分别进行插入排序,分组排序结果如下
 * [3, 8] [5, 9], [1, 4], [6, 7], [0, 2]
 * 整个数组排序结果如下:
 * [3, 5, 1, 6, 0, 8, 9, 4, 7, 2]
 * 可以看到,像3,5,6这些小元素都被调到前面了,然后缩小增量 gap=5/2=2,数组被分为2组:
 * [3, 1, 0, 9, 7], [5, 6, 8, 4, 2]
 * 对这2组再分别做插入排序,分组排序结果如下:
 * [0, 1, 3, 7, 9], [2, 4, 5, 6, 8]
 * 合并到整个数组的排序结果如下:
 * [0, 2, 1, 4, 3, 5, 7, 6, 9, 8]
 * 再缩小增量 gap=2/2=1, 此时, 整个数组就只有1组了:
 * [0, 2, 1, 4, 3, 5, 7, 6, 9, 8]
 * 经过上述分组排序,整个数组的有序化程度已经很高了(关键,高有序化可以大幅减少后续排序的移动工作量)
 * 此时,仅仅需要对上述数组简单微调,无序大量移动操作即可完成整个数组的排序
 * [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
 *
 * 应用实例:
 * init: {8,9,1,7,2,3,5,4,6,0} 从小到大排序, 分别使用交换法(可读性高,速度相对较慢),
 * 和移动法(可读性低,速度相对较快),并测试性能
 */
public class ShellSortTest {
    public static void main(String[] args) {
        int[] arr = newArr();
        //arr = new int[]{3, 9, -1, 10, -2};
        //arr = new int[]{8,9,1,7,2,3,5,4,6,0};
        //System.out.printf("待排序数组:%s\n", Arrays.toString(arr));
        long start = System.nanoTime();
        //testSwap(arr);
        long end = System.nanoTime();
        //System.out.printf("交换排序结果:%s\n", Arrays.toString(arr));
        // post: 13,914,711,000 纳秒,约14秒, 100000个元素的数组
        System.out.printf("交换法耗时:%d\n", (end-start));

        arr = newArr();
        //arr = new int[]{8,9,1,7,2,3,5,4,6,0};
        start = System.nanoTime();
        testMove(arr);
        end = System.nanoTime();
        //System.out.printf("移动排序结果:%s\n", Arrays.toString(arr));
        // post: 13452400 纳秒,约13毫秒, 100000个元素的数组
        // post: 55,089,846,900 纳秒, 约55秒, 1亿个元素
        System.out.printf("移动法耗时:%d\n", (end-start));

        arr = newArr();
        start = System.nanoTime();
        SelectSortTest.jdkSort(arr);
        end = System.nanoTime();
        // post: 4860200 纳秒, 约5毫秒, 100000个元素的数组
        // post: 15,026,837,900 纳秒, 约15秒, 1亿个元素
        System.out.printf("jdksort 耗时:%d\n", (end-start));
    }

    public static int[] newArr(){
        int[] arr = new int[100_000_000];
        for(int i=0; i<arr.length; i++){
            arr[i]=(int)(Math.random()*Integer.MAX_VALUE);
        }
        return arr;
    }

    public static void test1(int[] arr){
        int tmp=0;
        // 初始增量gap=length/2=5
        // 希尔排序第1轮
        // 将10个数组分成了5组
        // 外部循环遍历各组第1个元素
        for(int i=5; i<arr.length; i++){
            // 内部循环遍历各组第2个元素,这里步长-=5,与缩量相等,是为了取同组元素进行比较
            /**
             * init: [8, 9, 1, 7, 2, 3, 5, 4, 6, 0]
             * i=5,j=0,arr[j]=8,arr[i]==3
             * i=6,j=1,arr[j]=9,arr[i]==5
             * i=7,j=2,arr[j]=1,arr[i]==4
             * i=8,j=3,arr[j]=7,arr[i]==6
             * i=9,j=4,arr[j]=2,arr[i]==0
             */
            for(int j=i-5; j>=0; j-=5){
                // 如果当前元素大于假设步长后的那个元素,说明需要交换
                if(arr[j]>arr[j+5]){
                    tmp = arr[j];
                    arr[j]=arr[j+5];
                    arr[j+5]=tmp;
                }
            }
        }

        System.out.printf("第1轮排序后的数组:\n");
        System.out.printf("%s\n", Arrays.toString(arr));

        // 初始增量gap=5/2=2
        // 希尔排序第2轮
        // 将10个数组分成了2组
        /**
         * 第1轮排序后: [3, 5, 1, 6, 0, 8, 9, 4, 7, 2]
         * 1. i=2,j=0, ()表示i位置上的元素, []表示j位置上的元素, {}表示j+2位置上的元素
         * 1.1 [3], 5, {(1)}, 6, 0, 8, 9, 4, 7, 2
         * j>j+2,true,交换,[1], 5, {(3)}, 6, 0, 8, 9, 4, 7, 2
         * j-2>=0,false,下一轮
         * 2. i=3,j=1
         * 2.1 1, [5], 3, {(6)}, 0, 8, 9, 4, 7, 2
         * j>j+2,false,不变
         * j-2>=0,false,下一轮
         * 3. i=4,j=2
         * 3.1 1, 5, [3], 6, {(0)}, 8, 9, 4, 7, 2
         * j>j+2,true,交换, 1, 5, [0], 6, {(3)}, 8, 9, 4, 7, 2
         * j-2>=0,true,下一循环,j=0
         * 3.2 [1], 5, {0}, 6, 3, 8, 9, 4, 7, 2
         * j>j+2,true,交换, [0], 5, {1}, 6, 3, 8, 9, 4, 7, 2
         * 4. i=5,j=3
         * 4.1 0, 5, 1, [6], 3, {(8)}, 9, 4, 7, 2
         * j>j+2,false,不变
         * j-2>=0,true,下一循环,j=1
         * 4.2 0, [5], 1, {6}, 3, (8), 9, 4, 7, 2
         * j>j+2,false,不变
         * j-2>=0,false,下一轮
         * 5. i=6,j=4
         * 5.1 0, 5, 1, 6, [3], 8, {(9)}, 4, 7, 2
         * j>j+2,false,不变
         * j-2>=0,true,下一循环,j=2
         * 5.2 0, 5, [1], 6, {3}, 8, (9), 4, 7, 2
         * j>j+2,false,不变
         * j-2>=0,true,下一循环,j=0
         * 5.3 [0], 5, {1}, 6, 3, 8, (9), 4, 7, 2
         * j>j+2,false,不变
         * j-2>=0,false,下一轮
         * 6. i=7,j=5
         * 6.1 0, 5, 1, 6, 3, [8], 9, {(4)}, 7, 2
         * j>j+2,true,交换,0, 5, 1, 6, 3, [4], 9, {(8)}, 7, 2
         * j-2>=0,true,下一循环,j=3
         * 6.2 0, 5, 1, [6], 3, {4}, 9, (8), 7, 2
         * j>j+2,true,交换,0, 5, 1, [4], 3, {6}, 9, (8), 7, 2
         * j-2>=0,true,下一循环,j=1
         * 6.3 0, [5], 1, {4}, 3, 6, 9, (8), 7, 2
         * j>j+2,true,交换, 0, [4], 1, {5}, 3, 6, 9, (8), 7, 2
         * j-2>=0,false,下一轮
         * 7. i=8,j=6
         * 7.1 0, 4, 1, 5, 3, 6, [9], 8, {(7)}, 2
         * j>j+2,true,交换,0, 4, 1, 5, 3, 6, [7], 8, {(9)}, 2
         * j-2>=0,true,下一循环,j=4
         * 7.2 0, 4, 1, 5, [3], 6, {7}, 8, (9), 2
         * j>j+2,false,不变
         * j-2>=0,true,下一循环,j=2
         * 7.3 0, 4, [1], 5, {3}, 6, 7, 8, (9), 2
         * j>j+2,false,不变
         * j-2>=0,true,下一循环,j=0
         * 7.4 [0], 4, {1}, 5, 3, 6, 7, 8, (9), 2
         * 8. i=9,j=7
         * 8.1 0, 4, 1, 5, 3, 6, 7, [8], 9, {(2)}
         * j>j+2,true,交换, 0, 4, 1, 5, 3, 6, 7, [2], 9, {(8)}
         * j-2>=0,true,下一循环,j=4
         * 8.2 0, 4, 1, 5, 3, [6], 7, {2}, 9, (8)
         * j>j+2,true,交换, 0, 4, 1, 5, 3, [2], 7, {6}, 9, (8)
         * j-2>=0,true,下一循环,j=2
         * 8.3 0, 4, 1, [5], 3, {2}, 7, 6, 9, (8)
         * j>j+2,true,交换, 0, 4, 1, [2], 3, {5}, 7, 6, 9, (8)
         * j-2>=0,true,下一循环,j=0
         * 8.4 0, [4], 1, {2}, 3, 5, 7, 6, 9, (8)
         * j>j+2,true,交换, 0, [2], 1, {4}, 3, 5, 7, 6, 9, (8)
         * j-2>=0,false,下一轮
         * i=9,i<arr.length false, 结束
         */
        for(int i=2; i<arr.length; i++){
            // 内部循环遍历各组第j个元素,这里步长-=2,与缩量相等,是为了取同组元素进行比较
            for(int j=i-2; j>=0; j-=2){
                // 如果当前元素大于假设步长后的那个元素,说明需要交换
                if(arr[j]>arr[j+2]){
                    tmp = arr[j];
                    arr[j]=arr[j+2];
                    arr[j+2]=tmp;
                }
            }
        }

        System.out.printf("第2轮排序后的数组:\n");
        System.out.printf("%s\n", Arrays.toString(arr));

        // 初始增量gap=2/2=1
        // 希尔排序第3轮
        // 将10个数组分成了1组
        for(int i=1; i<arr.length; i++){
            // 内部循环遍历各组第j个元素,这里步长-=1,与缩量相等,是为了取同组元素进行比较
            for(int j=i-1; j>=0; j--){
                // 如果当前元素大于假设步长后的那个元素,说明需要交换
                if(arr[j]>arr[j+1]){
                    tmp = arr[j];
                    arr[j]=arr[j+1];
                    arr[j+1]=tmp;
                }
            }
        }

        System.out.printf("第3轮排序后的数组:\n");
        System.out.printf("%s\n", Arrays.toString(arr));
    }

    public static void test2(int[] arr){
        int tmp;
        int count=0;
        // 缩小增量排序,按增量分组,分组排序后缩小增量,直到增量为1,即对整个数组进行排序
        for(int gap=arr.length/2; gap>0; gap/=2) {
            //count++;
            for (int i = gap; i < arr.length; i++) {
                for (int j = i - gap; j >= 0; j-=gap) {
                    if (arr[j] > arr[j + gap]) {
                        tmp = arr[j];
                        arr[j] = arr[j + gap];
                        arr[j + gap] = tmp;
                    }
                }
            }
            //System.out.printf("第%d轮排序后的数组:\n", count);
            //System.out.printf("%s\n", Arrays.toString(arr));
        }
    }

    // 将test1,test2的交换法改为移动法
    public static void test3(int[] arr){
        int count=0;
        // 缩小增量排序,按增量分组,分组排序后缩小增量,直到增量为1,即对整个数组进行排序
        for(int gap=arr.length/2; gap>0; gap/=2) {
            //count++;
            // 从第gap个元素,逐个对其所在的组进行直接插入排序
            for(int i=gap; i<arr.length; i++){
                int j=i;
                int tmp=arr[i];
                if(arr[j]<arr[j-gap]){
                    while((j-gap)>=0 && tmp<arr[j-gap]){
                        // 移动
                        arr[j] = arr[j-gap];
                        j -= gap;
                    }
                    // 退出循环,表示找到了插入的位置
                    arr[j]=tmp;
                }
            }
            //System.out.printf("第%d轮排序后的数组:\n", count);
            //System.out.printf("%s\n", Arrays.toString(arr));
        }
    }

    public static void testSwap(int[] arr){
        int tmp;
        int count=0;
        // 缩小增量排序,按增量分组,分组排序后缩小增量,直到增量为1,即对整个数组进行排序
        for(int gap=arr.length/2; gap>0; gap/=2) {
            //count++;
            for (int i = gap; i < arr.length; i++) {
                for (int j = i - gap; j >= 0; j-=gap) {
                    if (arr[j] > arr[j + gap]) {
                        tmp = arr[j];
                        arr[j] = arr[j + gap];
                        arr[j + gap] = tmp;
                    }
                }
            }
            //System.out.printf("第%d轮排序后的数组:\n", count);
            //System.out.printf("%s\n", Arrays.toString(arr));
        }
    }
    public static void testMove(int[] arr) {
        int count=0;
        // 缩小增量排序,按增量分组,分组排序后缩小增量,直到增量为1,即对整个数组进行排序
        for(int gap=arr.length/2; gap>0; gap/=2) {
            //count++;
            // 从第gap个元素,逐个对其所在的组进行直接插入排序
            for(int i=gap; i<arr.length; i++){
                // 无序表头,待插入的元素
                int tmp=arr[i];
                // 有序表尾部索引
                int orderIdx=i-gap;
                // 从尾向头遍历有序表,比较有序表元素与无序表头的大小
                for(; orderIdx>=0 && tmp<arr[orderIdx]; orderIdx-=gap){
                    // 无序表头小于有序表元素,则当前有序表元素后移,为无序表头空出位置
                    // 等同于arr[i]=arr[orderIdx]; 因i=orderIdx+gap;
                    arr[orderIdx+gap]=arr[orderIdx];
                }
                // 退出循环,表示找到了插入的位置
                arr[orderIdx+gap]=tmp;
            }
            //System.out.printf("第%d轮排序后的数组:\n", count);
            //System.out.printf("%s\n", Arrays.toString(arr));
        }
    }
}
